package 二叉树的遍历;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @Author ：xu_xiaofeng.
 * @Date ：Created in 10:58 2021/2/17
 * @Description：
 */
public class BinaryTreeNode {
    int data;
    BinaryTreeNode leftChild = null;
    BinaryTreeNode rightChild = null;

    BinaryTreeNode(int data, BinaryTreeNode leftChild, BinaryTreeNode rightChild) {
        this.data = data;
        this.leftChild = leftChild;
        this.rightChild = rightChild;
    }
}

class test {
    /**
     * 二叉树前序遍历   根-> 左-> 右
     *
     * @param node 二叉树节点
     */
    public static void preOrderTraveralRescur(BinaryTreeNode node) {
        if (node == null) {
            return;
        }
        System.out.print(node.data + " ");
        preOrderTraveralRescur(node.leftChild);
        preOrderTraveralRescur(node.rightChild);
    }

    /**
     * 二叉树中序遍历   左-> 根-> 右
     *
     * @param node 二叉树节点
     */
    public static void inOrderTraveralRescur(BinaryTreeNode node) {
        if (node == null) {
            return;
        }
        System.out.print(node.data + " ");
        inOrderTraveralRescur(node.leftChild);
        inOrderTraveralRescur(node.rightChild);
    }

    /**
     * 二叉树后序遍历 左-> 右-> 根
     *
     * @param node
     */
    public static void postOrderTraveralRescur(BinaryTreeNode node) {
        // 递归结束条件
        if (node == null) {
            return;
        }
        postOrderTraveralRescur(node.leftChild);
        postOrderTraveralRescur(node.rightChild);
        System.out.print(node.data + " ");
    }

    public static void preOrderTraveral(BinaryTreeNode node) {
        Stack<BinaryTreeNode> stack = new Stack<>();

        BinaryTreeNode curNode = node;

        // 外层是为了出栈，当访问到叶节点（或者没有左孩子节点）时则使用栈中的元素节点
        while (curNode != null || !stack.isEmpty()) {

            // 访问到叶节点是节点后其子节点的值为null
            // 访问当前节点及左子节点
            while (curNode != null) {
                System.out.print(curNode.data + " ");
                stack.push(curNode);

                // 不断访问左孩子节点
                curNode = curNode.leftChild;
            }

            // 没有左孩子节点后，则弹出栈顶节点，访问右孩子
            if (!stack.isEmpty()) {
                curNode = stack.pop();
                curNode = curNode.rightChild;
            }


        }
    }

    public static void inOrderTraveral(BinaryTreeNode node) {
        Stack<BinaryTreeNode> stack = new Stack<>();

        BinaryTreeNode curNode = node;
        while (curNode != null || !stack.isEmpty()) {

            while (curNode != null) {
                stack.push(curNode);
                curNode = curNode.leftChild;
            }

            // 没有左孩子后，则出栈，依次访问当前节点、及右孩子节点
            if (!stack.isEmpty()) {
                curNode = stack.pop();

                System.out.print(curNode.data + " ");

                curNode = curNode.rightChild;
            }
        }
    }

    public static void levelOrder(BinaryTreeNode headNode) {

        Deque<BinaryTreeNode> queue = new LinkedList<>();

        // 将头节点入队
        queue.add(headNode);

        BinaryTreeNode curNode;
        while (!queue.isEmpty()) {
            curNode = queue.pop();
            System.out.print(curNode.data + " ");

            // 将孩子节点入队
            if (curNode.leftChild != null) {
                queue.add(curNode.leftChild);
            }
            if (curNode.rightChild != null) {
                queue.add(curNode.rightChild);
            }
        }

    }
}